package sit.engreal.leetcode.problems600;

import org.junit.jupiter.api.Assertions;

import java.util.HashMap;

/**
 * <a href="https://leetcode.cn/problems/permutation-in-string/">567. 字符串的排列</a>
 */
public class LeetCode567 {
    public boolean checkInclusion(String s1, String s2) {
        final HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            map.put(s1.charAt(i), 1 + map.getOrDefault(s1.charAt(i), 0));
        }
        int k = -1;
        int remain = s1.length();
        for (int j = 0; j < s2.length(); j++) {
            if (remain == 0) {
                return true;
            }

            final char ch = s2.charAt(j);
            final int count = map.getOrDefault(ch, -1);
            if (count < 0) {
                // map[ch] == -1 s1中没有字符ch [0, j] 都失败，从j+1开始搜索
                map.clear();
                for (int i = 0; i < s1.length(); i++) {
                    map.put(s1.charAt(i), 1 + map.getOrDefault(s1.charAt(i), 0));
                }
                remain = s1.length();
                k = j;
            } else if (count == 0) {
                // map[ch] 再次出现，[0, firstIndexOf(ch)]失败
                while (s2.charAt(++k) != ch) {
                    map.put(s2.charAt(k), 1 + map.getOrDefault(s2.charAt(k), 0));
                    remain++;
                }
            } else {
                // count > 0 匹配一次
                map.put(ch, count - 1);
                remain--;
            }
        }
        return remain == 0;
    }

    public static void main(String[] args) {
        final LeetCode567 demo = new LeetCode567();
        Assertions.assertFalse(demo.checkInclusion("hello", "ooolleoooleh"));
        Assertions.assertTrue(demo.checkInclusion("adc", "dcda"));
        Assertions.assertTrue(demo.checkInclusion("ab", "eidbaooo"));
        Assertions.assertFalse(demo.checkInclusion("ab", "eidboaoo"));
    }
}
